package SwordFingerOffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Q38_Permutation {
    //字符串全排列 ==> 遗忘 ==> 完全搞不懂了 ？

    //暴力递归
    public String[] permutation(String s) {
        if (s == null || s.length() == 0){
            return new String[]{};
        }
        HashSet<String> ans = new HashSet<>();
        process(s.toCharArray(), 0, ans);
        return ans.toArray(new String[]{});
    }

    public void process(char[] str, int index, HashSet<String> ans){
        if (index == str.length){
            ans.add(String.valueOf(str));
        }
        //在这里进行一波分支限界
        boolean[] isVisited = new boolean[26];
        for (int i = index; i < str.length; i++) {
            if (isVisited[str[i] - 'a']){
                continue;
            }
            //固定一个位置
            swap(str, index, i); // for 循环角度来看 当前位置 ==> a, b, c
            isVisited[str[i] - 'a'] = true;
            process(str, index + 1, ans);
            //恢复现场
            swap(str, index, i);
        }
    }

    public void swap(char[] str, int i, int j){
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}
